package leetcode.code005;

public class Solution extends Solution005 {

	@Override
	public String longestPalindrome(String s) {
		// abcddcbaabcddcba
		char[] chars = this.sharp(s);// [#, b, #, a, #, b, #, a, #, d, #]
		int[] radius = new int[chars.length];
		int center = -1;
		int range = -1;
		int max = -1;
		int start = -1;
		int end = -1;
		for (int i = 0; i < chars.length; i++) {
			radius[i] = range > i ? Math.min(radius[((center) << 1) - i], range - i) : 1;
			while (i + radius[i] < chars.length && i - radius[i] > -1) {
				if (chars[i + radius[i]] == chars[i - radius[i]]) {
					radius[i]++;
				} else {
					break;
				}
			}
			if (i + radius[i] > range) {
				range = i + radius[i];
				center = i;
			}
			if (radius[i] > max) {
				max = radius[i];
				start = center - radius[i] + 1;
				end = center + radius[i] - 1;
			}
		}
		StringBuffer sb = new StringBuffer();
		for (int i = start; i <= end; i++) {
			if (chars[i] != '#') {
				sb.append(chars[i]);
			}
		}
		return sb.toString();
	}

	private char[] sharp(String s) {
		char[] chars = new char[(s.length() << 1) | 1];
		int p = 0;
		for (int i = 0; i < chars.length; i++) {
			if ((i & 1) == 0) {
				chars[i] = '#';
			} else {
				chars[i] = s.charAt(p);
				p++;
			}
		}
		return chars;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
